from collections import deque

from dataStructure.tree.binarySearchTree import BinarySearchTree


class BreadthFirstSearch:
    def breadth_first_search(self, root, target):
        """
        Perform breadth-first search (BFS) on a tree starting from the given root node.

        Args:
            root: Root node of the tree.
            target: Target node to search for.

        Returns:
            List: Nodes visited during the search in the order they were visited.
                   If the target node is found, the list represents the path from the root to the target node.
                   If the target node is not found, an empty list is returned.
        """
        if not root:
            return []

        visited = set()
        queue = deque([(root, [])])

        while queue:
            node, path = queue.popleft()
            if node == target:
                return path + [node]

            if node not in visited:
                visited.add(node)
                for child in self.get_children(node):
                    queue.append((child, path + [node]))

        return []

    def bidirectional_breadth_first_search(self, start, target):
        """
        Perform bidirectional breadth-first search on the binary search tree to find the path between two nodes.

        Args:
            start: Start node for the search.
            target: Target node to search for.

        Returns:
            List: Nodes visited during the search in the order they were visited.
                   If a path is found, the list represents the path from the start node to the target node.
                   If no path is found, an empty list is returned.
        """
        if start is None or target is None:
            return []

        if start == target:
            return [start]

        forward_queue = deque([(start, None, [])])
        backward_queue = deque([(target, None, [])])
        forward_visited = set([start])
        backward_visited = set([target])
        common_node = None

        while forward_queue and backward_queue:
            forward_node, forward_parent, forward_path = forward_queue.popleft()
            backward_node, backward_parent, backward_path = backward_queue.popleft()

            if forward_node in backward_visited:
                common_node = forward_node
                break

            if backward_node in forward_visited:
                common_node = backward_node
                break

            if forward_node.left and forward_node.left not in forward_visited:
                forward_queue.append((forward_node.left, forward_node, forward_path + [forward_node]))
                forward_visited.add(forward_node.left)
            if forward_node.right and forward_node.right not in forward_visited:
                forward_queue.append((forward_node.right, forward_node, forward_path + [forward_node]))
                forward_visited.add(forward_node.right)

            if backward_node.left and backward_node.left not in backward_visited:
                backward_queue.append((backward_node.left, backward_node, backward_path + [backward_node]))
                backward_visited.add(backward_node.left)
            if backward_node.right and backward_node.right not in backward_visited:
                backward_queue.append((backward_node.right, backward_node, backward_path + [backward_node]))
                backward_visited.add(backward_node.right)

        if common_node is not None:
            forward_path = self._reconstruct_path(forward_path + [common_node])
            backward_path = self._reconstruct_path(backward_path + [common_node], backward_parent)[::-1]
            return forward_path + backward_path[1:]

        return []
    def _expand_forward_node(self, forward_queue, forward_visited, forward_parent, forward_node):
        """
        Expand the forward node by adding its neighbors to the queue.

        Args:
            forward_queue: Queue for forward traversal.
            forward_visited: Set of visited nodes in forward traversal.
            forward_parent: Dictionary of parent-child relationships in forward traversal.
            forward_node: Current node in forward traversal.
        """
        children = self.get_children(forward_node)
        for child in children:
            if child not in forward_visited:
                forward_queue.append(child)
                forward_visited.add(child)
                forward_parent[child] = forward_node

    def _expand_backward_node(self, backward_queue, backward_visited, backward_parent, backward_node):
        """
        Expand the backward node by adding its neighbors to the queue.

        Args:
            backward_queue: Queue for backward traversal.
            backward_visited: Set of visited nodes in backward traversal.
            backward_parent: Dictionary of parent-child relationships in backward traversal.
            backward_node: Current node in backward traversal.
        """
        children = self.get_children(backward_node)
        for child in children:
            if child not in backward_visited:
                backward_queue.append(child)
                backward_visited.add(child)
                backward_parent[child] = backward_node

    def _reconstruct_bidirectional_path(self, forward_parent, backward_parent, common_node):
        """
        Reconstruct the path from the start node to the common node in a bidirectional search.

        Args:
            forward_parent: Dictionary of parent-child relationships in forward traversal.
            backward_parent: Dictionary of parent-child relationships in backward traversal.
            common_node: Common node found in both forward and backward traversals.

        Returns:
            List: Nodes in the reconstructed path.
        """
        forward_path = self._reconstruct_path(forward_parent, common_node)
        backward_path = self._reconstruct_path(backward_parent, common_node)[::-1]
        return forward_path + backward_path[1:]

    def _reconstruct_path(self, parent, node):
        """
        Reconstruct the path from the start node to the given node.

        Args:
            parent: Dictionary of parent-child relationships.
            node: Target node.

        Returns:
            List: Nodes in the reconstructed path.
        """
        path = []
        while node is not None:
            path.append(node)
            node = parent[node]
        return path[::-1]

    def get_children(self, node):
        """
        Get the children nodes of the given node.

        Args:
            node: Node for which to retrieve the children.

        Returns:
            List: Children nodes of the given node.
        """
        if node is None:
            return []

        children = []
        if node.left:
            children.append(node.left)
        if node.right:
            children.append(node.right)
        return children

    def zero_one_breadth_first_search(self, root):
        """
        Perform 0-1 breadth-first search (0-1 BFS) on a tree starting from the given root node.

        Args:
            root: Root node of the tree.

        Returns:
            Dict: Shortest path weights from the root node to all other nodes in the tree.
                  If a node is unreachable from the root node, its weight is set to infinity.
        """
        if not root:
            return {}

        distance = {root: 0}
        queue = deque([(root, 0)])

        while queue:
            node, weight = queue.popleft()

            for child in self.get_children(node):
                edge_weight = self.get_edge_weight(node, child)
                new_weight = weight + edge_weight

                if child not in distance or new_weight < distance[child]:
                    distance[child] = new_weight

                    if edge_weight == 0:
                        queue.appendleft((child, new_weight))
                    else:
                        queue.append((child, new_weight))

        return distance

    def get_children(self, node):
        """
        Get the children nodes of the given node.

        Args:
            node: Node for which to retrieve the children.

        Returns:
            List: Children nodes of the given node.
        """
        children = []
        if node.left:
            children.append(node.left)
        if node.right:
            children.append(node.right)
        return children

    def get_edge_weight(self, node1, node2):
        """
        Get the weight of the edge between node1 and node2.

        Args:
            node1: First node.
            node2: Second node.

        Returns:
            int: Weight of the edge between the two nodes.
        """
        # Assuming all edges have a weight of 1 in this binary search tree
        return 1



if __name__ == "__main__":
    # Create a new binary search tree
    bst = BinarySearchTree()

    # Insert nodes into the binary search tree
    bst.insert(5)
    bst.insert(3)
    bst.insert(7)
    bst.insert(2)
    bst.insert(4)
    bst.insert(6)
    bst.insert(8)
    # for i in range(10, 20,2):
    #     bst.insert(i)

    # Print the binary search tree structure
    print("Binary Search Tree Structure:")
    print(bst)
    # Output:
    # Binary Search Tree Structure:
    #            __________Node(5)__________
    #           /                           \
    #     ___Node(3)___               ___Node(7)___
    #    /             \             /             \
    # Node(2)       Node(4)       Node(6)       Node(8)

    # Create an instance of BreadthFirstSearch
    bfs = BreadthFirstSearch()

    # Perform breadth-first search
    target_node = bst.root.right.right
    bfs_result = bfs.breadth_first_search(bst.root, target_node)
    print("Breadth-First Search:")
    for node in bfs_result:
        print(node)
    print()

    # Perform bidirectional breadth-first search
    # not work for more than two nodes
    bidirectional_bfs_result = bfs.bidirectional_breadth_first_search(bst.root, target_node)
    print("Bidirectional Breadth-First Search:")
    for node in bidirectional_bfs_result:
        print(node)
    print()

    # Perform 0-1 breadth-first search
    zero_one_bfs_result = bfs.zero_one_breadth_first_search(bst.root)
    print("0-1 Breadth-First Search:")
    for node, weight in zero_one_bfs_result.items():
        print(f"Node: {node}, Weight: {weight}")
